Golang

您所在的位置：网站首页 › golang map并发读写 › Golang

Golang

2023-09-09 14:55| 来源: 网络整理| 查看: 265

Golang - 分段锁实现并发安全Map 一.引言

我们一般有两种方式来降低锁的竞争：

第一种：减少锁的持有时间，sync.Map即是采用这种策略，通过冗余的数据结构，使得需要持有锁的时间，大大减少。第二种：降低锁的请求频率，锁分解和锁分段技术即是这种思想的体现。

锁分段技术又可称为分段锁机制

什么叫做分段锁机制？

将数据分为一段一段的存储，然后给每一段数据配备一把锁.

这样在多线程情况下，不同线程操作不同段的数据不会造成冲突，线程之间也不会存在锁竞争，有效的提高了并发访问的效率

二.实现原理

首先我们需要给数据进行分段，属于同一个段的数据放在一起，我们采用golang原生的map来充当段的容器，用于存储元素，将key通过哈希映射的形式分配到不同的段中。

// SharedMap 并发安全的小map,ShardCount 个这样的小map数组组成一个大map type SharedMap struct { items map[string]interface{} sync.RWMutex // 读写锁，保护items }

可以看到，我们给每个段都配备了一个内置的读写锁，用于保护段内的数据安全

// ShardCount 底层小shareMap数量 var ShardCount = 32 // ConcurrentHashMap 并发安全的大map，由 ShardCount 个小mao数组组成，方便实现分段锁机制 type ConcurrentHashMap []*SharedMap

然后 ShardCount 个ShareMap就组成了一个大的并发安全的map。

其哈希函数采用了著名的fnv函数

// fnv32 hash函数 func fnv32(key string) uint32 { // 著名的fnv哈希函数，由 Glenn Fowler、Landon Curt Noll和 Kiem-Phong Vo 创建 hash := uint32(2166136261) const prime32 = uint32(16777619) keyLength := len(key) for i := 0; i < keyLength; i++ { hash *= prime32 hash ^= uint32(key[i]) } return hash } 1.New // New 创建一个新的concurrent map. func New() ConcurrentHashMap { m := make(ConcurrentHashMap, ShardCount) for i := 0; i < ShardCount; i++ { m[i] = &SharedMap{items: make(map[string]interface{})} } return m }

直接采用make初始化指定数量个ShareMap，并采用数组的形式保证这些初始化好的ShareMap

2.Set/Get/Delete/Has // GetShardMap 返回给定key的sharedMap func (m ConcurrentHashMap) GetShardMap(key string) *SharedMap { return m[uint(fnv32(key))%uint(ShardCount)] } // Set 添加 key-value func (m ConcurrentHashMap) Set(key string, value interface{}) { // Get map shard. shard := m.GetShardMap(key) shard.Lock() shard.items[key] = value shard.Unlock() } // Get 返回指定key的value值 func (m ConcurrentHashMap) Get(key string) (interface{}, bool) { shard := m.GetShardMap(key) shard.RLock() val, ok := shard.items[key] shard.RUnlock() return val, ok } // Remove 删除一个元素 func (m ConcurrentHashMap) Remove(key string) { // Try to get shard. shard := m.GetShardMap(key) shard.Lock() delete(shard.items, key) shard.Unlock() } // Has 判断元素是否存在 func (m ConcurrentHashMap) Has(key string) bool { // Get shard shard := m.GetShardMap(key) shard.RLock() // See if element is within shard. _, ok := shard.items[key] shard.RUnlock() return ok }

都是先将key通过hash函数确定和获取其所属的ShareMap，然后锁住该段，直接操作数据。

3.Count/Keys // Count 统计元素总数 func (m ConcurrentHashMap) Count() int { count := 0 for i := 0; i < ShardCount; i++ { shard := m[i] shard.RLock() count += len(shard.items) shard.RUnlock() } return count }

遍历所有的ShareMap，逐个统计，注意，遍历的时候每个ShareMap时，都需要加锁

// Keys 以字符串数组的形式返回所有key func (m ConcurrentHashMap) Keys() []string { count := m.Count() ch := make(chan string, count) go func() { // Foreach shard. wg := sync.WaitGroup{} wg.Add(ShardCount) for _, shard := range m { go func(shard *SharedMap) { // Foreach key, value pair. shard.RLock() for key := range shard.items { ch

【本文地址】

Golang

Golang

今日新闻

推荐新闻